package com.lizk.sort;

/**
 * @author lizhikui
 * @date 2020/2/6 10:21
 */
public class InsertSort {

    /**
     * 插入排序的实现
     *
     * 插入排序的逻辑
     * 1.把数组的第一个元素当做已经排序的数组，其余的元素当做待排序的数组
     * 2.然后考察第二个元素，与第一个元素比较，根据比较结果，放到第一个元素的左边或右边，这个时候
     *   左边的前两个元素当做已经排好序的数组，其余的元素当做待排序数组
     * 3.然后考察第三个元素，与第二个元素比较，然后根据比较结果，放到第二个元素的左边或右边，再与第一个元素
     *   比较，根据比较结果，放到第一个元素的左边或右边。
     * 4.按照 2、3步骤，循环的比较，直到待排序的数组为空
     */
    public static Integer[] sort(Integer [] arrays){
        for (int i = 1 ; i < arrays.length; i ++){
            for (int j = i  ; j > 0 ; j--){
                if(arrays[j] < arrays[j - 1]){
                    SortUtils.swap(arrays,j,j - 1);
                }else{ //当前一个元素比后一个元素小的时候，说明当前要移动的元素已经放到了合适的位置，直接退出循环
                    break;
                }
            }
        }
        return arrays;
    }

    /**
     * 这个排序的写法，多用了一个变量的赋值，
     * 再数据量为50000的时候，与sort的排序写法已经有了明显的差距
     */
    public static Integer[] sort2(Integer [] arrays){
        for (int i = 1 ; i < arrays.length; i ++){
            int currIndex = i;
            for (int j = i - 1  ; j >= 0 ; j--){
                if(arrays[j] > arrays[currIndex]){
                    SortUtils.swap(arrays,j,currIndex);
                    currIndex = j;
                }else{ //当前一个元素比后一个元素小的时候，说明当前要移动的元素已经放到了合适的位置，直接退出循环
                    break;
                }
            }
        }
        return arrays;
    }

}
